package com.example.demo.suanfa_sort;

/**
 * @program: java_base
 * @description: 给定数组，给定子数组加和范围[a，b]范围，某个起点，从左某个起点向右加和；
 * 此和落在[a,b]范围 计数器加1
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/14 13:55
 */
// 这道题直接在leetcode测评：
// https://leetcode.com/problems/count-of-range-sum/
public class CountOfRangeSumDemo {


    /**
     * 返回前缀和数组
     *
     * @param arr
     * @return
     */
    public int[] arrSum(int[] arr) {
        int[] arrSum = new int[arr.length];
//        int sum = 0;
//        for (int i = 0; i <arr.length; i++) {
//            sum += arr[i];
//            arrSum[i] = sum;
//        }
        arrSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            arrSum[i] = arrSum[i - 1] + arr[i];
        }
        return arrSum;
    }

    public int process(int[] arr, int l, int r, int upper, int lower) {
        if (l == r) {
            if (arr[l] >= lower && arr[l] <= upper) {
                return 1;
            } else {
                return 0;
            }
        }
        int mid = l + ((r - l) >> 1);
        int leftCount = process(arr, l, mid, upper, lower);
        int rightCount = process(arr, mid + 1, r, upper, lower);
        int count = merge_first(arr, l, mid, r, upper, lower);
        return count + leftCount + rightCount;
    }


    private int merge_first(int[] arr, int l, int mid, int r, int upper, int lower) {
        // 不进行merge操作，先进行数组挑选
        // 右边元素X，求左边有多少个数，位于[X-upper, x-lower]
        // 边界条件

        // [L,R)
        int windowL = l;
        int windowR = l;
        int ans = 0;
        for (int i = mid + 1; i <= r; i++) {
            long min = arr[i] - upper;
            long max = arr[i] - lower;

            // windowL <= mid 一直推动着 arr[windowL] < min移动
            while (arr[windowL] < min && windowL <= mid){
                windowL++;
            }
            // windowL <= mid 一直推动着 arr[windowR] <= max 移动
            while (windowR <= mid && arr[windowR] <= max){
                windowR++;
            }
        }
//        ans += Math.max(0, windowR - windowL);
        // [L,R)
        ans += windowR - windowL;



        return 0;
    }


}
